package com.autumn.annotations.leetcode.leet;

import com.autumn.annotations.leetcode.basic.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * ClassName: TreeToLinkList
 *
 * @Description:
 * @Author: wangqiuyang
 * @Date: 2022/2/18 8:17 下午
 * History:
 * <author>          <time>          <version>          <desc>
 * wangqiuyang    2022/2/18 8:17 下午   @Version 1.0        描述
 */
public class TreeToLinkList {
    // 根左右
    public static void flatten(TreeNode root) {
        List<Integer> linkList = new ArrayList<>();
        // 二叉树先序遍历获得list
        getLinkedList(root,linkList);

        // list遍历 拼接到游节点下
        // 所有的左节点为null
        putListToTree(root,linkList);
    }

    public static void getLinkedList(TreeNode root , List<Integer> list) {
        if (root == null) return; // 递归终止

        list.add(root.val); // 根
        getLinkedList(root.left , list); // 左
        getLinkedList(root.right, list); // 右
    }

    public static void putListToTree(TreeNode root , List<Integer> list) {
        TreeNode head = root;
        for (int i = 0; i < list.size(); i++) {
            head.left = null;
            head.val = list.get(i);
            if ( i < list.size() - 1){
                // 如果是最后一个不添加右节点直接为null
                head.right = new TreeNode();
                head = head.right;
            }
        }
    }


    public static void main(String[] args) {
        TreeNode root1 = new TreeNode(1);
        TreeNode root2 = new TreeNode(2);
        TreeNode root3 = new TreeNode(3);
        TreeNode root4 = new TreeNode(4);
        TreeNode root5 = new TreeNode(5);
        TreeNode root6 = new TreeNode(6);
        root1.left = root2;
        root1.right = root5;
        root2.left = root3;
        root2.right = root4;
        root5.right = root6;

        flatten(root1);
    }
}
